;;; Collatz conjecture
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun iterative-next (n)
  (cond ((<= n 1) n)
		((evenp n) (/ n 2))
		((oddp n) (1+ (* n 3)))))

(defun iterative-seq-count (n)
  (do ((i 1 (1+ i)) (tn n (iterative-next tn)))
	  ((= tn 1) (cons n i))
	  ))

(defun p14 (&key (upper-limit 1000000))
  (first
	(sort (loop for i from 2 to upper-limit
		        collect (iterative-seq-count i))
          (lambda (x y) (>= (cdr x) (cdr y))))))

;;; 327 seconds !!!!!
(format t "~a~%" (time (p14 :upper-limit 1000))) 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; improve 1: make a table (array, hash, whatever) that holds the lengths already calculated for any starting position.
;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun collatz (i)
  (if (= i 1)
      1
      (+ 1 (collatz-cached (if (evenp i)
                               (/ i 2)
                               (+ (* 3 i) 1))))))
 
(let ((ht (make-hash-table)))
  (defun collatz-cached (n)
    (multiple-value-bind (value has-key) (gethash n ht)
      (if has-key
          value
          (setf (gethash n ht) (collatz n))))))
 
(defun problem-14 ()
  (let ((m 0) (a nil))
    (dotimes (tmp 999999)
      (let* ((s (1+ tmp))
             (c (collatz s)))
        (if (> c m)
            (setf m c
                  a s))))
    a))

;;; 13 seconds
;(format t "~a~%" (time (problem-14)))
